import binarySearch.BinarySearch;
import struct.TreeNode;

/**
 * @description: 算法草纸
 * @author: mayunfei
 * @date: 2024/1/28 14:18
 */
public class Write {

    public static void main(String[] args) {

    }

    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len + 1];
        int l = 1;
        arr[l] = nums[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] > arr[l]) {
                arr[++l] = nums[i];
            } else {
                int left = 1;
                int right = l;
                int pos = 0;
                while (left <= right) {
                    int mid = (left + right) >> 1;
                    if (arr[mid] >= nums[i]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                        pos = mid;
                    }
                }
                arr[pos + 1] = nums[i];
            }
        }
        return l;
    }

}
